1700D - River Locks - CodeForces Solution

#include<bits/stdc++.h>
#ifndef LOCAL
#define endl '\n'
#endif
#define ast cout << "debug" << endl
#define debug(n) cout << #n << " = " << n << endl
#define debugv( v ) for( auto e : v ) cout << e << endl
#define debugm( m ) for( auto [f, s] : m ) cout << f << " : " << s << endl;
using namespace std;
using ll = long long;
void solve()
{
    int n;
    cin >> n;
    vector<ll> v(n + 1);
    vector<ll> sum(n + 1);
    sum[0] = 0;
    for( int i = 1; i <= n; i++ ) {
        cin >> v[i];
        sum[i] = sum[i - 1] + v[i];
    }
    vector<ll> dp(n);
    dp[0] = v[1];
    ll now = 0;
    for( int i = 2; i <= n; i++ ) {
        if( now + dp[i - 2] >= v[i] ) {
            dp[i - 1] = dp[i - 2];
            now = now + dp[i - 2] - v[i];
        }
        else {
            ll need = v[i] - (now + dp[i - 2]);
            if( need % i == 0 ) {
                now = 0;
                dp[i - 1] = dp[i - 2] + need / i;
            }
            else {
                dp[i - 1] = dp[i - 2] + need / i + 1;
                now = (need / i + 1) * i - need;
            }
        }
    }
    int q;
    cin >> q;
    while( q-- ) {
        ll k;
        cin >> k;
        ll ans;
        if( sum[n] % k == 0 ) ans = sum[n] / k;
        else ans = sum[n] / k + 1;
        if( ans > n ) {
            cout << -1 << endl;
            continue;
        }
        if( dp[ans - 1] > k ) {
            cout << -1 << endl;
            continue;
        }
        cout << ans << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    #ifdef LOCAL
    system("pause");
    #endif
    return 0;
}